#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "list.h"
#include "skip_list.h"

static const unsigned int SKIP_LIST_MAX_LEVEL = 16;
static const float SKIP_LIST_POWER = 0.25;

typedef struct SkipListWrapper SkipListWrapper;

struct SkipListWrapper {
	void * data;
	SkipListIterator * nexts[];
};

struct SkipList {
	List * list;
	unsigned int level;
	FunctionLessThan lessThan;
	FunctionOnErased onErased;
};

// SkipListWrapper {

static SkipListWrapper * skipListWrapperNew(const void * data, int level);

static void skipListWrapperDelete(SkipListWrapper * wrapper);

static void * skipListWrapperData(const SkipListWrapper * wrapper);

static SkipListIterator * skipListWrapperNext(const SkipListWrapper * wrapper, int level);

static void skipListWrapperSetNext(SkipListWrapper * wrapper, int level, const SkipListIterator * next);

// }

// SkipListIterator {

static SkipListWrapper * skipListIteratorWrapper(const SkipListIterator * iterator);

static SkipListIterator * skipListIteratorWrapperNext(const SkipListIterator * iterator, int level);

static void skipListIteratorWrapperSetNext(SkipListIterator * iterator, int level, const SkipListIterator * next);

// }

// SkipList {

static SkipListIterator * skipListHead(const SkipList * list);

static int skipListRandom();

static SkipListIterator * skipListLowerBound(const SkipListIterator * first, const SkipListIterator * last, const void * data, FunctionLessThan lessThan);

// }

// SkipListWrapper {

static SkipListWrapper * skipListWrapperNew(const void * data, int level) {
	SkipListWrapper * tmp;

	if (level < 0) {
		return NULL;
	}

	tmp = (SkipListWrapper *)malloc(sizeof(SkipListWrapper) + level * sizeof(SkipListIterator *));
	memset(tmp, 0, malloc_usable_size(tmp));
	if (tmp == NULL) {
		return NULL;
	}

	tmp->data = (void *)data;

	return tmp;
}

static void skipListWrapperDelete(SkipListWrapper * wrapper) {
	assert(wrapper != NULL);

	free(wrapper);
}

static void * skipListWrapperData(const SkipListWrapper * wrapper) {
	assert(wrapper != NULL);

	return wrapper->data;
}

static SkipListIterator * skipListWrapperNext(const SkipListWrapper * wrapper, int level) {
	assert(wrapper != NULL && level >= 0);

	return wrapper->nexts[level];
}

static void skipListWrapperSetNext(SkipListWrapper * wrapper, int level, const SkipListIterator * next) {
	assert(wrapper != NULL && level >= 0);

	wrapper->nexts[level] = (SkipListIterator *)next;
}

// }

// SkipListIterator {

static SkipListWrapper * skipListIteratorWrapper(const SkipListIterator * iterator) {
	assert(iterator != NULL);

	return (SkipListWrapper *)linkedListIteratorData(iterator);
}

void * skipListIteratorData(const SkipListIterator * iterator) {
	assert(iterator != NULL);

	return skipListWrapperData((SkipListWrapper *)linkedListIteratorData(iterator));
}

static SkipListIterator * skipListIteratorWrapperNext(const SkipListIterator * iterator, int level) {
	assert(iterator != NULL);

	return skipListWrapperNext((SkipListWrapper *)linkedListIteratorData(iterator), level);
}

static void skipListIteratorWrapperSetNext(SkipListIterator * iterator, int level, const SkipListIterator * next) {
	assert(iterator != NULL);

	return skipListWrapperSetNext((SkipListWrapper *)linkedListIteratorData(iterator), level, next);
}

SkipListIterator * skipListIteratorPrev(const SkipListIterator * iterator) {
	return linkedListIteratorPrev(iterator);
}

SkipListIterator * skipListIteratorNext(const SkipListIterator * iterator) {
	return linkedListIteratorNext(iterator);
}

// }

// SkipList {

SkipList * skipListNew(FunctionLessThan lessThan, FunctionOnErased onErased) {
	SkipList * tmp;
	int i;

	if (lessThan == NULL) {
		return NULL;
	}

	tmp = (SkipList *)malloc(sizeof(SkipList));
	if (tmp == NULL) {
		return NULL;
	}
	memset(tmp, 0, sizeof(SkipList));

	tmp->list = linkedListNew(NULL, NULL, NULL);
	if (tmp->list == NULL) {
		free(tmp);
		return NULL;
	}
	tmp->level = 0;
	if (lessThan != NULL) {
		tmp->lessThan = lessThan;
	}
	else {
		tmp->lessThan = functionVoidLessThan;
	}
	tmp->onErased = onErased;

	SkipListWrapper * wrapper = skipListWrapperNew(NULL, SKIP_LIST_MAX_LEVEL);
	if (wrapper == NULL) {
		linkedListDelete(tmp->list);
		free(tmp);
		return NULL;
	}

	for (i = SKIP_LIST_MAX_LEVEL - 1; i >= 0; i--) {
		skipListWrapperSetNext(wrapper, i, skipListEnd(tmp));
	}

	if (linkedListInsert(tmp->list, skipListEnd(tmp), (void *)wrapper) == NULL) {
		skipListWrapperDelete(wrapper);
		linkedListDelete(tmp->list);
		free(tmp);
		return NULL;
	}

	return tmp;
}

void skipListDelete(SkipList * list) {
	SkipListIterator * iterator;

	assert(list != NULL);

	for (iterator = skipListHead(list); iterator != skipListEnd(list); iterator = skipListIteratorNext(iterator)) {
		skipListWrapperDelete(skipListIteratorWrapper(iterator));
	}
	linkedListDelete(list->list);
	free(list);
}

static SkipListIterator * skipListHead(const SkipList * list) {
	assert(list != NULL);

	return linkedListBegin(list->list);
}

SkipListIterator * skipListBegin(const SkipList * list) {
	return skipListIteratorNext(skipListHead(list));
}

SkipListIterator * skipListEnd(const SkipList * list) {
	assert(list != NULL);

	return linkedListEnd(list->list);
}

int skipListIsEmpty(const SkipList * list) {
	return skipListBegin(list) == skipListEnd(list);
}

void skipListClear(SkipList * list) {
	SkipListIterator * current;
	SkipListWrapper * wrapper;
	void * data;
	int i;

	assert(list != NULL);

	while (!skipListIsEmpty(list)) {
		current = skipListBegin(list);
		wrapper = skipListIteratorWrapper(current);
		data = skipListWrapperData(wrapper);

		linkedListErase(list->list, current);
		skipListWrapperDelete(wrapper);

		if (list->onErased != NULL) {
			list->onErased(data);
		}
	}

	for (i = list->level - 1; i >= 0; i--) {
		skipListIteratorWrapperSetNext(skipListHead(list), i, skipListEnd(list));
	}

	list->level = 0;
}

SkipListIterator * skipListInsert(SkipList * list, const void * data) {
	SkipListIterator * updates[SKIP_LIST_MAX_LEVEL];
	SkipListIterator * current;
	SkipListIterator * next;
	SkipListWrapper * wrapper;
	int level;
	int i;

	assert(list != NULL);

	memset(updates, 0, SKIP_LIST_MAX_LEVEL * sizeof(SkipListIterator *));

	current = skipListHead(list);
	next = skipListEnd(list);
	for (i = list->level - 1; i >= 0; i--) {
		for (;;) {
			next = skipListIteratorWrapperNext(current, i);
			if (next == skipListEnd(list)) {
				break;
			}
			else if (!list->lessThan(skipListIteratorData(next), data)) {
				break;
			}
			current = next;
		}
		updates[i] = current;
	}

	current = skipListLowerBound(skipListIteratorNext(current), next, data, list->lessThan);
	if (current != skipListEnd(list) && !list->lessThan(data, skipListIteratorData(current))) {
		return NULL;
	}

	level = skipListRandom();
	if (level > list->level) {
		for (i = list->level; i < level; i++) {
			updates[i] = skipListHead(list);
		}
		list->level = level;
	}

	wrapper = skipListWrapperNew(data, level);
	if (wrapper == NULL) {
		return NULL;
	}

	current = linkedListInsert(list->list, current, (void *)wrapper);
	if (current == NULL) {
		skipListWrapperDelete(wrapper);
		return NULL;
	}

	for (i = 0; i < level; i++) {
		skipListIteratorWrapperSetNext(current, i, skipListIteratorWrapperNext(updates[i], i));
		skipListIteratorWrapperSetNext(updates[i], i, current);
	}

	return current;
}

SkipListIterator * skipListErase(SkipList * list, const void * data) {
	assert(list != NULL);

	skipListEraseIf(list, data, list->lessThan, list->lessThan);
}

SkipListIterator * skipListEraseIf(SkipList * list, const void * key, FunctionLessThan lessThanKey, FunctionLessThan keyLessThan) {
	SkipListIterator * updates[SKIP_LIST_MAX_LEVEL];
	SkipListIterator * current;
	SkipListIterator * next;
	SkipListWrapper * wrapper;
	void * data;
	int i;

	assert(list != NULL && lessThanKey != NULL && keyLessThan != NULL);

	memset(updates, 0, SKIP_LIST_MAX_LEVEL * sizeof(SkipListIterator *));

	current = skipListHead(list);
	next = skipListEnd(list);
	for (i = list->level - 1; i >= 0; i--) {
		for (;;) {
			next = skipListIteratorWrapperNext(current, i);
			if (next == skipListEnd(list)) {
				break;
			}
			else if (!lessThanKey(skipListIteratorData(next), key)) {
				break;
			}
			current = next;
		}
		updates[i] = current;
	}

	current = skipListLowerBound(skipListIteratorNext(current), next, key, lessThanKey);
	if (current == skipListEnd(list) || keyLessThan(key, skipListIteratorData(current))) {
		return NULL;
	}

	wrapper = skipListIteratorWrapper(current);
	data = skipListWrapperData(wrapper);

	next = linkedListErase(list->list, current);
	if (next == NULL) {
		return NULL;
	}

	for (i = list->level - 1; i >= 0; i--) {
		if (skipListIteratorWrapperNext(updates[i], i) == current) {
			break;
		}
	}
	for (; i >= 0; i--) {
		skipListIteratorWrapperSetNext(updates[i], i, skipListWrapperNext(wrapper, i));
	}
	for (i = list->level - 1; i >= 0; i--) {
		if (skipListIteratorWrapperNext(skipListHead(list), i) == skipListEnd(list)) {
			list->level--;
		}
		else {
			break;
		}
	}

	skipListWrapperDelete(wrapper);

	if (list->onErased != NULL) {
		list->onErased(data);
	}

	return next;
}

SkipListIterator * skipListFind(const SkipList * list, const void * data) {
	assert(list != NULL);

	skipListFindIf(list, data, list->lessThan, list->lessThan);
}

SkipListIterator * skipListFindIf(const SkipList * list, const void * key, FunctionLessThan lessThanKey, FunctionLessThan keyLessThan) {
	SkipListIterator * current;
	SkipListIterator * next;
	int i;

	assert(list != NULL && lessThanKey != NULL && keyLessThan != NULL);

	current = skipListHead(list);
	next = skipListEnd(list);
	for (i = list->level - 1; i >= 0; i--) {
		for (;;) {
			next = skipListIteratorWrapperNext(current, i);
			if (next == skipListEnd(list)) {
				break;
			}
			else if (!lessThanKey(skipListIteratorData(next), key)) {
				break;
			}
			current = next;
		}
	}

	current = skipListLowerBound(skipListIteratorNext(current), next, key, lessThanKey);
	if (current == skipListEnd(list) || keyLessThan(key, skipListIteratorData(current))) {
		return NULL;
	}
	else {
		return current;
	}
}

void skipListPrint(const SkipList * list) {
	SkipListIterator * iterator;
	int i;

	assert(list != NULL);

	for (i = -1; i < (int)(list->level); i++) {
		printf("[%d]\t", i);
	}
	printf("\n");
	iterator = skipListHead(list);
	for (i = -1; i < (int)((malloc_usable_size(skipListIteratorWrapper(iterator)) - sizeof(SkipListWrapper)) / sizeof(SkipListIterator *)); i++) {
		if (i == -1) {
			printf("> %d\t", *(int *)skipListIteratorData(skipListIteratorNext(iterator)));
		}
		else if (skipListIteratorWrapperNext(iterator, i) != NULL) {
			if (skipListIteratorWrapperNext(iterator, i) != skipListEnd(list)) {
				printf("> %d\t", *(int *)skipListIteratorData(skipListIteratorWrapperNext(iterator, i)));
			}
			else {
				printf(">\t");
			}
		}
	}
	printf("\n");
	for (iterator = skipListBegin(list); iterator != skipListEnd(list); iterator = skipListIteratorNext(iterator)) {
		for (i = -1; i < (int)((malloc_usable_size(skipListIteratorWrapper(iterator)) - sizeof(SkipListWrapper)) / sizeof(SkipListIterator *)); i++) {
			if (i == -1) {
				printf("%d\t", *(int *)skipListIteratorData(iterator));
			}
			else if (skipListIteratorWrapperNext(iterator, i) != NULL) {
				if (skipListIteratorWrapperNext(iterator, i) != skipListEnd(list)) {
					printf("%d > %d\t", *(int *)skipListIteratorData(iterator), *(int *)skipListIteratorData(skipListIteratorWrapperNext(iterator, i)));
				}
				else {
					printf("%d >\t", *(int *)skipListIteratorData(iterator));
				}
			}
		}
		printf("\n");
	}
}

void skipListPrintSize(const SkipList * list) {
	SkipListIterator * iterator;
	int i;
	int size;

	assert(list != NULL);

	for (i = list->level - 1; i >= 0; i--) {
		size = 0;
		for (iterator = skipListIteratorWrapperNext(skipListHead(list), i); iterator != skipListEnd(list); iterator = skipListIteratorWrapperNext(iterator, i)) {
			size++;
		}
		printf("Level[%d] size: %d\n", i, size);
	}
	size = 0;
	for (iterator = skipListBegin(list); iterator != skipListEnd(list); iterator = skipListIteratorNext(iterator)) {
		size++;
	}
	printf("Level[-1] size: %d\n", size);
}

static int skipListRandom() {
	int level = 0;
	while ((random() & 0xFFFF) < (SKIP_LIST_POWER * 0xFFFF)) {
		level += 1;
	}
	return (level < SKIP_LIST_MAX_LEVEL) ? level : SKIP_LIST_MAX_LEVEL;
}

static SkipListIterator * skipListLowerBound(const SkipListIterator * first, const SkipListIterator * last, const void * key, FunctionLessThan lessThan) {
	const SkipListIterator * current;
	for (current = first; current != last; current = skipListIteratorNext(current)) {
		if (!lessThan(skipListIteratorData(current), key)) {
			return (SkipListIterator *)current;
		}
	}
	return (SkipListIterator *)last;
}

// }

// SkipListForInt {

SkipList * skipListForIntNew() {
	return skipListNew(functionIntLessThan, functionIntOnErased);
}

SkipListIterator * skipListForIntInsert(SkipList * list, int data) {
	int * tmp;

	tmp = (int *)malloc(sizeof(int));
	if (tmp == NULL) {
		return NULL;
	}
	*tmp = data;

	return skipListInsert(list, tmp);
}

SkipListIterator * skipListForIntErase(SkipList * list, int data) {
	return skipListErase(list, &data);
}

SkipListIterator * skipListForIntFind(const SkipList * list, int data) {
	return skipListFind(list, &data);
}

// }

// SkipListForUInt {

SkipList * skipListForUIntNew() {
	return skipListNew(functionUIntLessThan, functionUIntOnErased);
}

SkipListIterator * skipListForUIntInsert(SkipList * list, unsigned int data) {
	unsigned int * tmp;

	tmp = (unsigned int *)malloc(sizeof(unsigned int));
	if (tmp == NULL) {
		return NULL;
	}
	*tmp = data;

	return skipListInsert(list, tmp);
}

SkipListIterator * skipListForUIntErase(SkipList * list, unsigned int data) {
	return skipListErase(list, &data);
}

SkipListIterator * skipListForUIntFind(const SkipList * list, unsigned int data) {
	return skipListFind(list, &data);
}

// }
